package com.lw.leetcode.binary.c;

/**
 * Created with IntelliJ IDEA.
 * 2106. 摘水果
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/2 9:16
 */
public class MaxTotalFruits {

    public static void main(String[] args) {
        MaxTotalFruits test = new MaxTotalFruits();

        // 9
//        int[][] arr = {{2, 8}, {6, 3}, {8, 6}};
//        int startPos = 5;
//        int k = 4;

        // 14
//        int[][] arr = {{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}};
//        int startPos = 5;
//        int k = 4;

        // 0
//        int[][] arr = {{0, 3}, {6, 4}, {8, 5}};
//        int startPos = 3;
//        int k = 2;

        // 0[[200000,10000]]
        //200000
        //200000
        int[][] arr = {{200000,10000}};
        int startPos = 200000;
        int k = 200000;

        int i = test.maxTotalFruits(arr, startPos, k);
        System.out.println(i);
    }

    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int length = fruits.length;
        int[] arr = new int[length + 1];
        int s = -1;
        boolean flag = false;
        for (int i = 0; i < length; i++) {
            arr[i + 1] = arr[i] + fruits[i][1];
            if (fruits[i][0] < startPos) {
                s = i;
            } else if (fruits[i][0] == startPos) {
                flag = true;
            }
        }
        int max = 0;
        for (int i = 0; i <= s; i++) {
            if (startPos - fruits[i][0] > k) {
                continue;
            }
            int a = find(fruits, s + 1,length - 1, k + (fruits[i][0] << 1) - startPos + 1);
            int v =  arr[s + 1] -  arr[i] + (flag ?  fruits[s + 1][1] : 0);
            if (a > -1) {
                v = arr[a + 1] - arr[i];
            }
            max = Math.max(max, v);
        }
        for (int i = s + 1; i < length; i++) {
            if (fruits[i][0] - startPos > k) {
                break;
            }
            int a = find2(fruits, 0, s, (fruits[i][0] << 1) - k - startPos - 1);
            int v = arr[i + 1] - arr[s + 1 ];
            if (a > -1) {
                v = arr[i + 1] - arr[a];
            }
            max = Math.max(max, v);
        }
        return max;
    }

    private int find(int[][] fruits, int st,int end, int t) {
        if (st >= fruits.length || fruits[st][0] >= t) {
            return -1;
        }
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (fruits[m][0] < t) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

    private int find2(int[][] fruits, int st,int end,  int t) {
        if (end < 0 || fruits[end][0] <= t) {
            return -1;
        }
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (fruits[m][0] > t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
